 /*******************************************************************************
  * Copyright (c) 2000, 2007 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  * IBM Corporation - initial API and implementation
  * Martin Oberhuber (Wind River) - [105554] handle cyclic symbolic links
  *******************************************************************************/
 package org.eclipse.core.internal.localstore;

 import java.io.IOException ;
 import java.util.*;
 import java.util.regex.Pattern ;
 import org.eclipse.core.filesystem.*;
 import org.eclipse.core.internal.resources.*;
 import org.eclipse.core.internal.utils.Queue;
 import org.eclipse.core.resources.IContainer;
 import org.eclipse.core.resources.IResource;
 import org.eclipse.core.runtime.*;

 /**
  * Represents the workspace's tree merged with the file system's tree.
  */
 public class UnifiedTree {
     /** special node to mark the separation of a node's children */
     protected static final UnifiedTreeNode childrenMarker = new UnifiedTreeNode(null, null, null, null, false);

     private static final Iterator EMPTY_ITERATOR = Collections.EMPTY_LIST.iterator();

     /** special node to mark the beginning of a level in the tree */
     protected static final UnifiedTreeNode levelMarker = new UnifiedTreeNode(null, null, null, null, false);

     private static final IFileInfo[] NO_CHILDREN = new IFileInfo[0];

     /** Singleton to indicate no local children */
     private static final IResource[] NO_RESOURCES = new IResource[0];

     /**
      * True if the level of the children of the current node are valid according
      * to the requested refresh depth, false otherwise
      */
     protected boolean childLevelValid = false;

     /** an IFileTree which can be used to build a unified tree*/
     protected IFileTree fileTree = null;

     /** Spare node objects available for reuse */
     protected ArrayList freeNodes = new ArrayList();
     /** tree's actual level */
     protected int level;
     /** our queue */
     protected Queue queue;
     
     /** path prefixes for checking symbolic link cycles */
     protected PrefixPool pathPrefixHistory, rootPathHistory;

     /** tree's root */
     protected IResource root;

     /**
      * The root must only be a file or a folder.
      */
     public UnifiedTree(IResource root) {
         setRoot(root);
     }

     /**
      * Pass in a a root for the tree, a file tree containing all of the entries for this
      * tree and a flag indicating whether the UnifiedTree should consult the fileTree where
      * possible for entries
      * @param root
      * @param fileTree
      */
     public UnifiedTree(IResource root, IFileTree fileTree) {
         this(root);
         this.fileTree = fileTree;
     }

     public void accept(IUnifiedTreeVisitor visitor) throws CoreException {
         accept(visitor, IResource.DEPTH_INFINITE);
     }

     public void accept(IUnifiedTreeVisitor visitor, int depth) throws CoreException {
         Assert.isNotNull(root);
         initializeQueue();
         setLevel(0, depth);
         while (!queue.isEmpty()) {
             UnifiedTreeNode node = (UnifiedTreeNode) queue.remove();
             if (isChildrenMarker(node))
                 continue;
             if (isLevelMarker(node)) {
                 if (!setLevel(getLevel() + 1, depth))
                     break;
                 continue;
             }
             if (visitor.visit(node))
                 addNodeChildrenToQueue(node);
             else
                 removeNodeChildrenFromQueue(node);
             //allow reuse of the node
 freeNodes.add(node);
         }
     }

     protected void addChildren(UnifiedTreeNode node) {
         Resource parent = (Resource) node.getResource();

         // is there a possibility to have children?
 int parentType = parent.getType();
         if (parentType == IResource.FILE && !node.isFolder())
             return;

         //don't refresh resources in closed or non-existent projects
 if (!parent.getProject().isAccessible())
             return;

         // get the list of resources in the file system
 // don't ask for local children if we know it doesn't exist locally
 IFileInfo[] list = node.existsInFileSystem() ? getLocalList(node) : NO_CHILDREN;
         int localIndex = 0;

         // See if the children of this resource have been computed before
 ResourceInfo resourceInfo = parent.getResourceInfo(false, false);
         int flags = parent.getFlags(resourceInfo);
         boolean unknown = ResourceInfo.isSet(flags, ICoreConstants.M_CHILDREN_UNKNOWN);

         // get the list of resources in the workspace
 if (!unknown && (parentType == IResource.FOLDER || parentType == IResource.PROJECT) && parent.exists(flags, true)) {
             IResource target = null;
             UnifiedTreeNode child = null;
             IResource[] members;
             try {
                 members = ((IContainer) parent).members(IContainer.INCLUDE_TEAM_PRIVATE_MEMBERS);
             } catch (CoreException e) {
                 members = NO_RESOURCES;
             }
             int workspaceIndex = 0;
             //iterate simultaneously over file system and workspace members
 while (workspaceIndex < members.length) {
                 target = members[workspaceIndex];
                 String name = target.getName();
                 IFileInfo localInfo = localIndex < list.length ? list[localIndex] : null;
                 int comp = localInfo != null ? name.compareTo(localInfo.getName()) : -1;
                 //special handling for linked resources
 if (target.isLinked()) {
                     //child will be null if location is undefined
 child = createChildForLinkedResource(target);
                     workspaceIndex++;
                     //if there is a matching local file, skip it - it will be blocked by the linked resource
 if (comp == 0)
                         localIndex++;
                 } else if (comp == 0) {
                     // resource exists in workspace and file system --> localInfo is non-null
 //create workspace-only node for symbolic link that creates a cycle
 if (localInfo.getAttribute(EFS.ATTRIBUTE_SYMLINK) && localInfo.isDirectory() && isRecursiveLink(node.getStore(), localInfo))
                         child = createNode(target, null, null, true);
                     else
                         child = createNode(target, null, localInfo, true);
                     localIndex++;
                     workspaceIndex++;
                 } else if (comp > 0) {
                     // resource exists only in file system
 //don't create a node for symbolic links that create a cycle
 if (!localInfo.getAttribute(EFS.ATTRIBUTE_SYMLINK) || !localInfo.isDirectory() || !isRecursiveLink(node.getStore(), localInfo))
                         child = createChildNodeFromFileSystem(node, localInfo);
                     localIndex++;
                 } else {
                     // resource exists only in the workspace
 child = createNode(target, null, null, true);
                     workspaceIndex++;
                 }
                 if (child != null)
                     addChildToTree(node, child);
             }
         }

         /* process any remaining resource from the file system */
         addChildrenFromFileSystem(node, list, localIndex);

         /* Mark the children as now known */
         if (unknown) {
             // Don't open the info - we might not be inside a workspace-modifying operation
 resourceInfo = parent.getResourceInfo(false, false);
             if (resourceInfo != null)
                 resourceInfo.clear(ICoreConstants.M_CHILDREN_UNKNOWN);
         }

         /* if we added children, add the childMarker separator */
         if (node.getFirstChild() != null)
             addChildrenMarker();
     }

     protected void addChildrenFromFileSystem(UnifiedTreeNode node, IFileInfo[] childInfos, int index) {
         if (childInfos == null)
             return;
         for (int i = index; i < childInfos.length; i++) {
             IFileInfo info = childInfos[i];
             //don't create a node for symbolic links that create a cycle
 if (!info.getAttribute(EFS.ATTRIBUTE_SYMLINK) || !info.isDirectory() || !isRecursiveLink(node.getStore(), info))
                 addChildToTree(node, createChildNodeFromFileSystem(node, info));
         }
     }

     protected void addChildrenMarker() {
         addElementToQueue(childrenMarker);
     }

     protected void addChildToTree(UnifiedTreeNode node, UnifiedTreeNode child) {
         if (node.getFirstChild() == null)
             node.setFirstChild(child);
         addElementToQueue(child);
     }

     protected void addElementToQueue(UnifiedTreeNode target) {
         queue.add(target);
     }

     protected void addNodeChildrenToQueue(UnifiedTreeNode node) {
         /* if the first child is not null we already added the children */
         /* If the children won't be at a valid level for the refresh depth, don't bother adding them */
         if (!childLevelValid || node.getFirstChild() != null)
             return;
         addChildren(node);
         if (queue.isEmpty())
             return;
         //if we're about to change levels, then the children just added
 //are the last nodes for their level, so add a level marker to the queue
 UnifiedTreeNode nextNode = (UnifiedTreeNode) queue.peek();
         if (isChildrenMarker(nextNode))
             queue.remove();
         nextNode = (UnifiedTreeNode) queue.peek();
         if (isLevelMarker(nextNode))
             addElementToQueue(levelMarker);
     }

     protected void addRootToQueue() {
         //don't refresh in closed projects
 if (!root.getProject().isAccessible())
             return;
         IFileStore store = ((Resource) root).getStore();
         IFileInfo fileInfo = fileTree != null ? fileTree.getFileInfo(store) : store.fetchInfo();
         UnifiedTreeNode node = createNode(root, store, fileInfo, root.exists());
         if (node.existsInFileSystem() || node.existsInWorkspace())
             addElementToQueue(node);
     }

     /**
      * Creates a tree node for a resource that is linked in a different file system location.
      */
     protected UnifiedTreeNode createChildForLinkedResource(IResource target) {
         IFileStore store = ((Resource) target).getStore();
         return createNode(target, store, store.fetchInfo(), true);
     }

     /**
      * Creates a child node for a location in the file system. Does nothing and returns null if the location does not correspond to a valid file/folder.
      */
     protected UnifiedTreeNode createChildNodeFromFileSystem(UnifiedTreeNode parent, IFileInfo info) {
         IPath childPath = parent.getResource().getFullPath().append(info.getName());
         int type = info.isDirectory() ? IResource.FOLDER : IResource.FILE;
         IResource target = getWorkspace().newResource(childPath, type);
         return createNode(target, null, info, false);
     }

     /**
      * Factory method for creating a node for this tree. If the file exists on
      * disk, either the parent store or child store can be provided. Providing
      * only the parent store avoids creation of the child store in cases where
      * it is not needed. The store object is only needed for directories for
      * simple file system traversals, so this avoids creating store objects
      * for all files.
      */
     protected UnifiedTreeNode createNode(IResource resource, IFileStore store, IFileInfo info, boolean existsWorkspace) {
         //first check for reusable objects
 UnifiedTreeNode node = null;
         int size = freeNodes.size();
         if (size > 0) {
             node = (UnifiedTreeNode) freeNodes.remove(size - 1);
             node.reuse(this, resource, store, info, existsWorkspace);
             return node;
         }
         //none available, so create a new one
 return new UnifiedTreeNode(this, resource, store, info, existsWorkspace);
     }

     protected Iterator getChildren(UnifiedTreeNode node) {
         /* if first child is null we need to add node's children to queue */
         if (node.getFirstChild() == null)
             addNodeChildrenToQueue(node);

         /* if the first child is still null, the node does not have any children */
         if (node.getFirstChild() == null)
             return EMPTY_ITERATOR;

         /* get the index of the first child */
         int index = queue.indexOf(node.getFirstChild());

         /* if we do not have children, just return an empty enumeration */
         if (index == -1)
             return EMPTY_ITERATOR;

         /* create an enumeration with node's children */
         List result = new ArrayList(10);
         while (true) {
             UnifiedTreeNode child = (UnifiedTreeNode) queue.elementAt(index);
             if (isChildrenMarker(child))
                 break;
             result.add(child);
             index = queue.increment(index);
         }
         return result.iterator();
     }

     protected int getLevel() {
         return level;
     }

     protected IFileInfo[] getLocalList(UnifiedTreeNode node) {
         try {
             final IFileStore store = node.getStore();
             IFileInfo[] list = fileTree != null ? fileTree.getChildInfos(store) : store.childInfos(EFS.NONE, null);
             if (list == null)
                 return NO_CHILDREN;
             int size = list.length;
             if (size > 1)
                 quickSort(list, 0, size - 1);
             return list;
         } catch (CoreException e) {
             //treat failure to access the directory as a non-existent directory
 return NO_CHILDREN;
         }
     }

     protected Workspace getWorkspace() {
         return (Workspace) root.getWorkspace();
     }

     protected void initializeQueue() {
         //initialize the queue
 if (queue == null)
             queue = new Queue(100, false);
         else
             queue.reset();
         //initialize the free nodes list
 if (freeNodes == null)
             freeNodes = new ArrayList(100);
         else
             freeNodes.clear();
         //clear any known path prefixes for recursive symbolic link checking
 if (pathPrefixHistory != null) {
             pathPrefixHistory.clear();
             rootPathHistory.clear();
         }
         addRootToQueue();
         addElementToQueue(levelMarker);
     }

     protected boolean isChildrenMarker(UnifiedTreeNode node) {
         return node == childrenMarker;
     }

     protected boolean isLevelMarker(UnifiedTreeNode node) {
         return node == levelMarker;
     }

     private static class PatternHolder {
         //Initialize-on-demand Holder class to avoid compiling Pattern if never needed
 //Pattern: A UNIX relative path that just points backward
 public static Pattern trivialSymlinkPattern = Pattern.compile("\\.[./]*"); //$NON-NLS-1$
 }

     /**
      * Initialize history stores for symbolic links.
      * This may be done when starting a visitor, or later on demand.
      */
     protected void initLinkHistoriesIfNeeded() {
         if (pathPrefixHistory==null) {
             pathPrefixHistory = new PrefixPool(20);
             rootPathHistory = new PrefixPool(20);
         }
         if (rootPathHistory.size()==0) {
             //add current root to history
 IFileStore rootStore = ((Resource) root).getStore();
             try {
                 java.io.File rootFile = rootStore.toLocalFile(EFS.NONE, null);
                 if (rootFile!=null) {
                     IPath rootProjPath = root.getProject().getLocation();
                     if (rootProjPath!=null) {
                         try {
                             java.io.File rootProjFile = new java.io.File (rootProjPath.toOSString());
                             rootPathHistory.insertShorter(rootProjFile.getCanonicalPath()+'/');
                         } catch(IOException ioe) {
                             /*ignore here*/
                         }
                     }
                     rootPathHistory.insertShorter(rootFile.getCanonicalPath()+'/');
                 }
             } catch(CoreException e) {
                 /*ignore*/
             } catch(IOException e) {
                 /*ignore*/
             }
         }
     }
     
     /**
      * Check if the given child represents a recursive symbolic link.
      * <p>
      * On remote EFS stores, this check is not exhaustive and just
      * finds trivial recursive symbolic links pointing up in the tree.
      * </p><p>
      * On local stores, where {@link java.io.File#getCanonicalPath()}
      * is available, the test is exhaustive but may also find some
      * false positives with transitive symbolic links. This may lead
      * to suppressing duplicates of already known resources in the
      * tree, but it will never lead to not finding a resource at
      * all. See bug 105554 for details.
      * </p>
      * @param parentStore EFS IFileStore representing the parent folder
      * @param localInfo child representing a symbolic link
      * @return <code>true</code> if the given child represents a
      * recursive symbolic link.
      */
     private boolean isRecursiveLink(IFileStore parentStore, IFileInfo localInfo) {
         //Try trivial pattern first - works also on remote EFS stores
 String linkTarget = localInfo.getStringAttribute(EFS.ATTRIBUTE_LINK_TARGET);
         if (linkTarget!=null && PatternHolder.trivialSymlinkPattern.matcher(linkTarget).matches()) {
             return true;
         }
         //Need canonical paths to check all other possibilities
 try {
             java.io.File parentFile = parentStore.toLocalFile(EFS.NONE, null);
             //If this store cannot be represented as a local file, there is nothing we can do
 //In the future, we could try to resolve the link target
 //against the remote file system to do more checks.
 if (parentFile == null)
                 return false;
             //get canonical path for both child and parent
 java.io.File childFile = new java.io.File (parentFile, localInfo.getName());
             String parentPath = parentFile.getCanonicalPath()+'/';
             String childPath = childFile.getCanonicalPath()+'/';
             //get or instantiate the prefix and root path histories.
 //Might be done earlier - for now, do it on demand.
 initLinkHistoriesIfNeeded();
             //insert the parent for checking loops
 pathPrefixHistory.insertLonger(parentPath);
             if (pathPrefixHistory.containsAsPrefix(childPath)) {
                 //found a potential loop: is it spanning up a new tree?
 if (!rootPathHistory.insertShorter(childPath)) {
                     //not spanning up a new tree, so it is a real loop.
 return true;
                 }
             } else if (rootPathHistory.hasPrefixOf(childPath)) {
                 //child points into a different portion of the tree that we visited already before, or will certainly visit.
 //This does not introduce a loop yet, but introduces duplicate resources.
 //TODO Ideally, such duplicates should be modelled as linked resources. See bug 105534
 return false;
             } else {
                 //child neither introduces a loop nor points to a known tree.
 //It probably spans up a new tree of potential prefixes.
 rootPathHistory.insertShorter(childPath);
             }
         } catch (IOException e) {
             //ignore
 } catch (CoreException e) {
             //ignore
 }
         return false;
     }

     protected boolean isValidLevel(int currentLevel, int depth) {
         switch (depth) {
             case IResource.DEPTH_INFINITE :
                 return true;
             case IResource.DEPTH_ONE :
                 return currentLevel <= 1;
             case IResource.DEPTH_ZERO :
                 return currentLevel == 0;
             default :
                 return currentLevel + 1000 <= depth;
         }
     }

     /**
      * Sorts the given array of strings in place. This is
      * not using the sorting framework to avoid casting overhead.
      */
     protected void quickSort(IFileInfo[] infos, int left, int right) {
         int originalLeft = left;
         int originalRight = right;
         IFileInfo mid = infos[(left + right) / 2];
         do {
             while (mid.compareTo(infos[left]) > 0)
                 left++;
             while (infos[right].compareTo(mid) > 0)
                 right--;
             if (left <= right) {
                 IFileInfo tmp = infos[left];
                 infos[left] = infos[right];
                 infos[right] = tmp;
                 left++;
                 right--;
             }
         } while (left <= right);
         if (originalLeft < right)
             quickSort(infos, originalLeft, right);
         if (left < originalRight)
             quickSort(infos, left, originalRight);
         return;
     }

     /**
      * Remove from the last element of the queue to the first child of the
      * given node.
      */
     protected void removeNodeChildrenFromQueue(UnifiedTreeNode node) {
         UnifiedTreeNode first = node.getFirstChild();
         if (first == null)
             return;
         while (true) {
             if (first.equals(queue.removeTail()))
                 break;
         }
         node.setFirstChild(null);
     }

     /**
      * Increases the current tree level by one. Returns true if the new
      * level is still valid for the given depth
      */
     protected boolean setLevel(int newLevel, int depth) {
         level = newLevel;
         childLevelValid = isValidLevel(level + 1, depth);
         return isValidLevel(level, depth);
     }

     private void setRoot(IResource root) {
         this.root = root;
     }
 }

